package divideAndConquer;

public class Solution23 {
    //使用分治算法来做
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists.length==0){
            return null;
        }
        ListNode merged = merge(lists, 0, lists.length - 1);
        return merged;
    }

    //升序
    //合并两个列表
    public ListNode mergeTwoLists(ListNode l1,ListNode l2){
        //设置虚拟头节点
        ListNode dummy = new ListNode(-1);
        ListNode p = dummy;

        ListNode p1 = l1;
        ListNode p2 = l2;

        while(p1 != null && p2 != null){
            if (p1.val> p2.val){
                p.next = p2;
                p2 = p2.next;
            } else {
                p.next = p1;
                p1 = p1.next;
            }
            p = p.next;
        }

        if(p1 == null){
            p.next = p2;
        }

        if (p2 == null){
            p.next = p1;
        }

        return dummy.next;
    }

    public ListNode merge(ListNode[] lists,int left,int right){

        if (left==right){
            return lists[left];
        }

        int mid = (left + right) / 2;

        ListNode leftNode = merge(lists,left,mid);
        ListNode rightNode = merge(lists,mid+1,right);

        ListNode mergeList = mergeTwoLists(leftNode,rightNode);

        return mergeList;
    }
}
